Lập lịch là quá trình phân bổ, sắp xếp thứ tự và ấn định thời điểm thực thi các công việc hoặc tiến trình trên tập hợp tài nguyên hữu hạn nhằm tối ưu hóa các chỉ tiêu hiệu năng xác định như thời gian hoàn thành, thời gian chờ và mức độ sử dụng tài nguyên.
Bản chất lý thuyết và mô hình hóa bài toán lập lịch
Trong khoa học máy tính, kỹ nghệ hệ thống và nghiên cứu vận trù học (operations research), bài toán lập lịch (scheduling problem) liên quan đến việc gán các công việc cho các máy hoặc tài nguyên trong những khoảng thời gian cụ thể. Theo khuôn khổ phân loại lý thuyết kinh điển của Graham và cộng sự (1979), một bài toán lập lịch chuẩn được đặc trưng bởi mô hình phân loại:
- Môi trường máy: Xác định cấu hình phần cứng như máy đơn (single machine), máy song song (parallel machines), xưởng dòng (flow shop), xưởng mở rộng (job shop) hoặc xưởng mở (open shop).
- Đặc tính công việc: Quy định các ràng buộc thực thi như thời gian giải phóng (release times), thời hạn chót (deadlines), quan hệ thứ tự ưu tiên (precedence constraints) hay khả năng ngắt quãng (preemption).
- Hàm mục tiêu: Mục tiêu tối ưu cần đạt được như giảm thiểu tổng thời gian hoàn thành công việc (makespan), tổng độ trễ (total tardiness) hoặc tổng trọng số thời gian lưu lại trong hệ thống.
Các thuật toán lập lịch CPU kinh điển trong hệ điều hành
Trong kiến trúc hệ điều hành máy tính, bộ điều phối CPU (CPU scheduler) quyết định tiến trình nào trong hàng đợi sẵn sàng (ready queue) sẽ được cấp phát bộ xử lý. Giáo trình chuyên khảo của Peter Brucker (2004) đã phân loại chi tiết các thuật toán điều phối cốt lõi:
| Thuật toán | Cơ chế ngắt quãng | Tiêu chí lựa chọn | Ưu điểm | Hạn chế chính |
|---|---|---|---|---|
| FCFS (First-Come, First-Served) | Không ngắt quãng (Non-preemptive) | Tiến trình đến trước được phục vụ trước | Đơn giản, chi phí tính toán thấp | Hiệu ứng đoàn tàu (Convoy effect), thời gian chờ trung bình cao |
| SJF (Shortest Job First) | Cả hai dạng (Preemptive / Non-preemptive) | Ưu tiên tiến trình có thời gian thực thi ngắn nhất | Tối ưu hóa thời gian chờ trung bình tối thiểu | Khó dự đoán chính xác thời gian CPU burst, dễ gây bỏ đói tiến trình dài (Starvation) |
| Round Robin (RR) | Có ngắt quãng (Preemptive) | Phân bổ theo lát cắt thời gian luân phiên (Time quantum) | Công bằng, phản hồi nhanh cho hệ thống chia sẻ thời gian | Hiệu năng phụ thuộc nhiều vào độ dài time quantum; overhead chuyển ngữ cảnh cao |
| Lập lịch theo mức ưu tiên (Priority) | Cả hai dạng | Tiến trình có độ ưu tiên cao nhất được cấp CPU | Hỗ trợ tốt các tác vụ thời gian thực và khẩn cấp | Nguy cơ bỏ đói tiến trình ưu tiên thấp (cần kỹ thuật tăng tuổi - aging) |
| Hàng đợi phản hồi nhiều mức (MLFQ) | Có ngắt quãng (Preemptive) | Tự động điều chỉnh mức ưu tiên dựa trên hành vi tiến trình | Linh hoạt, tối ưu đồng thời cả tác vụ I/O bound và CPU bound | Phức tạp nhất trong thiết kế và tinh chỉnh tham số |
Độ phức tạp tính toán và các phương pháp giải quyết
Theo chuyên khảo của Michael L. Pinedo (2016), phần lớn các bài toán lập lịch trong thực tế (đặc biệt là bài toán Flow Shop và Job Shop từ 3 máy trở lên) đều thuộc lớp bài toán NP-hard. Do đó, việc tìm kiếm nghiệm tối ưu toàn cục bằng các thuật toán chính xác như quy hoạch nguyên (Integer Programming) hay duyệt nhánh cận (Branch and Bound) chỉ khả thi với quy mô bài toán nhỏ.
Đối với các hệ thống quy mô công nghiệp lớn, các kỹ sư thường áp dụng phương pháp xấp xỉ (heuristic) và thuật giải phỏng sinh học (metaheuristic) như giải thuật di truyền (Genetic Algorithm), tối ưu hóa bầy đàn (PSO) hoặc ủ thép (Simulated Annealing) để tìm ra lời giải gần tối ưu trong thời gian chấp nhận được.
Ứng dụng hiện đại trong điện toán đám mây và hệ thống thời gian thực
Trong kỷ nguyên trung tâm dữ liệu và điện toán đám mây quy mô lớn, bài toán lập lịch phát triển sang hướng quản lý tài nguyên phân tán đa chiều (CPU, RAM, băng thông mạng, GPU). Các hệ thống điều phối container hiện đại như Kubernetes áp dụng thuật toán lập lịch nâng cao kết hợp giữa ràng buộc về mức độ tương thích (affinity/anti-affinity), tiêu chí tiết kiệm năng lượng (green scheduling) và thỏa thuận mức dịch vụ (SLA) nhằm tối đa hóa hiệu suất toàn cụm máy chủ.